package Leetcode.图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static Leetcode.图.GraphUtils.getGraph;

/**
 * @Author: kirito
 * @Date: 2024/9/8 16:05
 * @Description: 给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。
 * 给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。
 *
 * 返回图中 完全连通分量 的数量。
 *
 * 如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，
 * 则称其为 连通分量 。
 *
 * 如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量 。
 * 示例 1：
 *
 * 输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
 * 输出：3
 * 解释：如上图所示，可以看到此图所有分量都是完全连通分量。
 * 示例 2：
 * 输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
 * 输出：1
 * 解释：包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
 * 包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
 * 因此，在图中完全连接分量的数量是 1 。
 */

public class 统计完全连通分量的数量 {
    int ans = 0;
    int e, v;
    /**
     * 完全图 边数=n*(n-1)/2
     * 统计每个连通图中的边数是否符合上述条件
     *
     * @param n n个点
     * @param edges 边
     * @return  统计完全连通分量的数量
     */
    public int countCompleteComponents(int n, int[][] edges) {
        List<Integer>[] graph = getGraph(n, edges);

        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                //新的一次dfs代表进入了一个新的连通分量中，新分量中重置e V
                e = 0;
                v = 0;
                dfs(graph, visited, i);
                //DFS 每个连通块，统计当前连通块的顶点数 v 和边数 e。
                //每访问一个点，就把 v 加一。
                //e 加上点 v 的邻居个数。注意这样一条边会统计两次。 所以下方判断条件就不用除以2
                if (e == v * (v - 1)) {
                    ans++;
                }
            }
        }
        return ans;
    }



    private void dfs(List<Integer>[] graph, boolean[] visited, int i) {
        visited[i] = true;
        v++;    //顶点数+1
        e += graph[i].size();   //边数+他的邻居数  即邻接表的所有元素个数
        for (int vertex : graph[i]) {
            if (!visited[vertex]) {
                dfs(graph, visited, vertex);
            }
        }
    }
}
